import java.util.*;
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }

    /**
     * 最长递增子序列
     * @param nums
     * @return
     */
    public static int lengthOfLIS(int[] nums) {
        //方法1：贪心加二分
//        int n=nums.length;
//        ArrayList<Integer> ret=new ArrayList<>();
//        ret.add(nums[0]);
//        for(int i=1;i<n;i++){
//            if(nums[i]>ret.get(ret.size()-1)){
//                ret.add(nums[i]);
//            }else{
//                int left=0,right=ret.size()-1;
//                while(left<right){
//                    int mid=(left+right)/2;
//                    if(ret.get(mid)<nums[i]){
//                        left=mid+1;
//                    }else{
//                        right=mid;
//                    }
//                }
//                ret.set(left,nums[i]);
//            }
//        }
//        return ret.size();
        //方法2：动态规划
        int n=nums.length;
        int[] dp=new int[n];
        dp[0]=1;
        int max=1;
        for(int i=1;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }

    /**
     * 判断是否互为字符重拍
     * @param s1
     * @param s2
     * @return
     */
    public static boolean CheckPermutation(String s1, String s2) {
        int n1=s1.length();
        int n2=s2.length();
        if(n1!=n2) return false;
        int[] hash=new int[26];
        for(int i=0;i<n1;i++){
            hash[s1.charAt(i)-'a']++;
        }
        for(int i=0;i<n2;i++){
            hash[s2.charAt(i)-'a']--;
            if(hash[s2.charAt(i)-'a']<0){
                return false;
            }
        }
        return true;
    }
}